//方法一：数学方法：sum1 - sum2
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum1 = (1+n)*n/2;
        int sum2 = 0;
        for(int i=0;i<n;i++) {
            sum2 += nums[i];
        }
        return sum1-sum2;
    }
}

//方法二：原数组和0-n不断异或
class Solution {
    public int missingNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i<nums.length;i++) {
            ret ^= i;
            ret ^= nums[i];
        }
        //因为0-n多一个元素
        ret ^= nums.length;

        return  ret;
    }
}

// 方法三：哈希集合：将数组元素放入哈希集合，然后依次检查找出消失的元素
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> Set = new HashSet<Integer>();
        int n = nums.length;

        for(int i = 0;i<n;i++) {
            Set.add(nums[i]);
        }
        int ret = 0;

        for(int i = 0; i<= n;i++) {
            if(!Set.contains(i)) {
                ret = i;
                break;
            }
        }
        return ret;
    }
}


